package LeetCode.题库.中等;


/**
 * @author 挚爱之夕
 * @date 2022-03-08 - 03 - 08 - 21:13
 * @Description '*'表示盘子 '|' 表示蜡烛
 * 同时给你一个下标从 0开始的二维整数数组queries，其中queries[i] = [lefti, righti]表示
 * 子字符串s[lefti...righti]（包含左右端点的字符）
 * 对于每个查询，你需要找到子字符串中在两支蜡烛之间的盘子的数目
 * 如果一个盘子在子字符串中左边和右边都至少有一支蜡烛，那么这个盘子满足在两支蜡烛之间
 * @Version 中等
 */
public class _2055蜡烛之间的盘子 {

    /*by me 超时了*/
    public int[] platesBetweenCandles(String s, int[][] queries) {
        int[] res = new int[queries.length];
        int[] query;
        int left, right;
        for (int i = 0; i < queries.length; i++) {
            query = queries[i];
            left = query[0];
            right = query[1];
            res[i] = find(s, left, right);
        }
        return res;
    }

    /*
    返回区间内满足条件的盘子个数
     */
    public int find(String s, int left, int right) {
        int res = 0, count = 0;
        //表示已经遍历过蜡烛
        boolean flag = false;
        for (int i = left; i <= right; i++) {
            if (!flag && s.charAt(i) == '|')
                flag = true;
            if (flag && s.charAt(i) == '|') {
                res += count;
                count = 0;
                continue;
            }
            if (flag) {
                count++;
            }
        }
        return res;
    }

    /*官方思路*/
    /*
    1.寻找蜡烛
    寻找给定区间最左侧个最右侧的蜡烛
    2.计算盘子数量
    这两个蜡烛之间盘子的数量
     */
    public int[] platesBetweenCandles1(String s, int[][] queries) {
        int n = s.length();
        /*预处理*/
        //记录从下标0到当前下标处，盘子的个数
        //通过这个可以得到两个蜡烛之间盘子的个数
        int[] preSum = new int[n];
        for (int i = 0, sum = 0; i < n; i++) {
            if (s.charAt(i) == '*') {
                sum++;
            }
            preSum[i] = sum;
        }
        //记录当前下标处最近左侧蜡烛下标，如果当前是蜡烛则是自己的下标
        int[] left = new int[n];
        for (int i = 0, l = -1; i < n; i++) {
            if (s.charAt(i) == '|') {
                l = i;
            }
            left[i] = l;
        }
        //记录当前下标处最近右侧蜡烛下标，如果当前是蜡烛则是自己的下标
        int[] right = new int[n];
        for (int i = n - 1, r = -1; i >= 0; i--) {
            if (s.charAt(i) == '|') {
                r = i;
            }
            right[i] = r;
        }
        int[] ans = new int[queries.length];
        for (int i = 0; i < queries.length; i++) {
            int[] query = queries[i];
            //x:给定区间最左边蜡烛的下标
            //y:给定区间最右边蜡烛的下标
            int x = right[query[0]], y = left[query[1]];
            ans[i] = x == -1 || y == -1 || x >= y ? 0 : preSum[y] - preSum[x];
        }
        return ans;
    }

}
